home *** CD-ROM | disk | FTP | other *** search
/ Chip 1996 April / CHIP 1996 aprilis (CD06).zip / CHIP_CD06.ISO / hypertxt.arj / 9511 / LEPESKIV.CD < prev    next >
Text File  |  1996-03-10  |  14KB  |  237 lines
  1.           @VLépéskiválasztás logikai játékokban@N
  2.  
  3.           @VHat gyalog@N
  4.  
  5.               Logikai és táblás játékprogramok írásakor a legkeményebb
  6.           dió  nem a  tetszetôs kezelôfelület  elkészítése, hanem  egy
  7.           erôs számítógépes ellenfél programjának megírása.
  8.               Bár  a  mai  gépek számítási  kapacitása  igen  nagy, az
  9.           úgynevezett  ""állapotrobbanás"  miatt  a  legtöbb   logikai
  10.           játékhoz  nem lehet  minden elôzetes  meggondolás nélkül,  a
  11.           ""nyers   erô"   módszerével   elfogadható   szinten  játszó
  12.           programot írni.  îgy a  számítógépes játékok  elméletéhez is
  13.           nagy matematikai, algoritmuselméleti apparátus alakult ki.
  14.               E     cikk    ismerteti     a    játékok     matematikai
  15.           reprezentációjának néhány  módszerét, majd  a legjobb  lépés
  16.           kiválasztására  szolgáló,  általánosan  elterjedt   @Kminimax,@N
  17.           illetve  @Kalfa-béta@N  eljárást,  de  a  konkrét  megvalósítás,
  18.           kódolás  kérdéseire nem  tér ki.  A módszerek  alkalmazhatók
  19.           szinte minden olyan játékra, melyben két, egymással  szemben
  20.           álló  játékos  (esetünkben  az  egyik  mindig  a számítógép)
  21.           rögzített szabályok  szerint egy  szintén jól  definiált cél
  22.           (gyôztes helyzet)  elérése érdekében  felváltva ""lép".  Egy
  23.           adott szituációban a választható lépések száma mindig véges.
  24.           A véletlen szerepe a játékokban nulla.
  25.  
  26.  
  27.           @VJátékok reprezentálása@N
  28.  
  29.               A  játékállás mindazon  információk összessége,  amelyek
  30.           egy játék menete során egy adott pillanatban az addig  elért
  31.           szituációt  leírják.  A   korábbi  lépések  az   elkövetkezô
  32.           állásokat   csak   a   pillanatnyi   játékálláson  keresztül
  33.           befolyásolhatják,  így  a  pillanatnyi  játékállás  elegendô
  34.           információt tartalmaz  a játékos  számára a  következô lépés
  35.           kiválasztásához.  Például  a  sakkban  a  táblán  lévô bábuk
  36.           elhelyezkedése és  az, hogy  lehet-e még  sáncolni, valamint
  37.           hogy   melyik   oldal  lép   legközelebb,   együtt  adja   a
  38.           játékállást. Kitüntetett szerepe van  a kezdô és a  befejezô
  39.           állásoknak.    (Ezeket    egyértelmûen    meghatározzák    a
  40.           játékszabályok.)
  41.               Ha a játékállások  száma véges, a  játék reprezentálható
  42.           az  állapotdiagrammal.  Ez   egy  olyan  gráf,   amelyben  a
  43.           játékállások alkotják a  csúcsokat, és a  lehetséges lépések
  44.           irányított élek a régi állásból az újba.
  45.               Sok szempontból célszerûbb lehet a játékfa  alkalmazása.
  46.           Ez abban különbözik az állapotdiagramtól, hogy ha ugyanaz  a
  47.           játékállás többféle elôzménnyel  is elérhetô, akkor  mindnek
  48.           külön csúcsot veszünk fel. Belátható, hogy így  gráfelméleti
  49.           értelemben fagráfot  kapunk. Szokás  a játékfa  éleit lefelé
  50.           irányítani, így a  kezdô állás, vagyis  a gyökér (0.  szint)
  51.           alatt  az  egy  lépésben  elérhetô  állások  szerepelnek (1.
  52.           szint),  alatta  a  két lépésben  elérhetô  állások,  és így
  53.           tovább. Ha  a két  játékos felváltva  lép, akkor  a fában is
  54.           váltják egymást a két játékos lépéslehetôségeinek  megfelelô
  55.           szintek.
  56.               Ha nincs korlátozva a lépések száma, a fa akár  végtelen
  57.           is  lehet, bár  az egy  szinten elhelyezkedô  csúcsok  száma
  58.           mindig véges. Ha minden csúcsnak @Kk@N darab fia van (@Kk@N él indul
  59.           ki belôle),  akkor az  @Kn.@N szinten  már @Kkⁿ@N  darab csúcs  van,
  60.           tehát az úgynevezett  állapotrobbanás miatt a  csúcsok száma
  61.           általában még véges esetben is olyan nagy, hogy a játékfának
  62.           csak egy részfája vizsgálható egyszerre.
  63.  
  64.  
  65.           @VA statikus állásértékelô függvény@N
  66.  
  67.               Mint  megállapítottuk,   egy  játékállásból   egyszerûen
  68.           meghatározhatók az adott helyzetben lehetséges lépések,  így
  69.           a   játékfa   könnyen  felépíthetô.   A   legjobb  lépés   a
  70.           játékfa(-részlet)   vizsgálatával   választható   ki.  Ehhez
  71.           szükség lesz arra, hogy két állást ""jóság" (mennyire vannak
  72.           közel   a    gyôzelemhez)   szempontjából    össze   tudjunk
  73.           hasonlítani. Az  összehasonlításhoz az  úgynevezett statikus
  74.           állásértékelô  függvényt  használjuk,  ami  egy  tetszôleges
  75.           álláshoz egy számszerû értéket (""jóságot") rendel.  Gyôztes
  76.           állás jósága  plusz végtelen  (vagy egy  nagyon nagy  szám),
  77.           vesztes állásé pedig mínusz végtelen.
  78.               Az értékelô függvény elôállítására nincsenek matematikai
  79.           módszerek.    Åltalában    a    sok    játékkal     szerzett
  80.           tapasztalatainkat kell egyetlen formulába öntenünk.
  81.               Szem elôtt kell tartanunk, hogy programunk csak  annyira
  82.           játszhat  jól,  amennyire  reális  az  értékelô függvényünk.
  83.           Különösen nehéz  a jó  állásértékelô függvény  megalkotása a
  84.           sakknál.
  85.  
  86.  
  87.           @VLépéskiválasztás minimax és alfa-béta eljárásokkal@N
  88.  
  89.               Egy adott  állás mellett  a legjobb  következô lépést az
  90.           alábbi minimax eljárással választhatjuk ki.
  91.               Ållítsuk  elô  az adott  állásból  az összes  lehetséges
  92.           folytatás  generálásával  a   játékfát  @Kn@N  szint   mélységig
  93.           (feltételezve, hogy @Kn@N  lépéssel gondolkodunk elôre).  Ezután
  94.           állapítsuk meg a legalsó  szinten lévô állások ""jóságát"  a
  95.           statikus  értékelô   függvénnyel.  Nevezzük   el  azokat   a
  96.           csúcsokat, amelyek után az ellenfél jön @KVAGY@N csomópontoknak,
  97.           míg a többit @KÉS@N csomópontnak! (A játékfában a @KVAGY@N és az  @KÉS@N
  98.           csúcsokat tartalmazó szintek felváltva következnek.)
  99.               Ésszerû  feltételezés,  hogy  mindkét  játékos  mindig a
  100.           számára legjobb lépést választja. Ez számunkra a legnagyobb,
  101.           az  ellenfél  számára  a legkisebb  értékû  állás.  Ha tehát
  102.           például az @Kn-1.@N szinten mi lépünk (@KÉS@N szint), akkor  minden,
  103.           az  @Kn-1.@N  szinten   lévô  csomópontnál  a   belôle  elérhetô
  104.           állásokból  a legnagyobb  értékû csúcsot  választjuk ki,  és
  105.           ennek értékét ""felvisszük". îgy végigmenve a  csomópontokon
  106.           már  a  teljes  @Kn-1.@N szintet  kiértékeljük.  Ezután  az @Kn-2.@N
  107.           szinten (@KVAGY@N szint) az  ellenfél mindig a legkisebb  értékû
  108.           fiú csomópontot  választja, és  ennek értékét  viszi fel. Az
  109.           eljárást  alulról  felfelé haladva  egészen  a fa  gyökeréig
  110.           végezzük.   Végül   az   elsô   szint   legnagyobb    értékû
  111.           csomópontjának megfelelô lépést tesszük meg.
  112.               Idônyerô észrevétel, hogy  miután az ellenfél  válaszolt
  113.           lépésünkre,  az   új  lépés   kiválasztásához  már   részben
  114.           rendelkezésre  áll a  játékfa, csupán  egy szinttel  lejjebb
  115.           kell menni. Természetesen a legjobb értékek felvitelét  újra
  116.           el kell végezni, így csak a játékfa létrehozásán  spóroltunk
  117.           valamennyit.
  118.               Ha   a   fa   generálásakor   egybôl   kiértékeljük    a
  119.           csomópontokat,  a   fa  felesleges   ágainak  ""levágásával"
  120.           szintén sok  idôt nyerhetünk.  Ugyanis ha  például egy olyan
  121.           szinten, ahol mi  lépünk, plusz végtelen  értékû csomópontot
  122.           találunk,  akkor  ennek  közvetlen  szomszédaival  és   azok
  123.           leszármazottaival   nem   kell   foglalkoznunk,   hiszen   a
  124.           gyôzelemnél  (plusz  végtelen  érték)  jobb  folytatás   nem
  125.           képzelhetô el. (Ugyanez a  helyzet az ellenfél lépéseinél  a
  126.           mínusz végtelennel.)
  127.  
  128.  
  129.           @VAz alfa-béta eljárás@N
  130.  
  131.               Hasonló megtakarítás nemcsak közvetlen nyerési lehetôség
  132.           esetén  érhetô el.  Ezen alapszik  az úgynevezett  alfa-béta
  133.           eljárás,   mely  a   minimax  módszer   továbbfejlesztésének
  134.           tekinthetô.
  135.               A játékfát  mélység szerinti  bejárással generáljuk.  Ez
  136.           azt   jelenti,   hogy   egy   csomópont    leszármazottainak
  137.           bejárásakor sorban bejárjuk a fiait (rekurzió) úgy, hogy egy
  138.           új fiúra  csak akkor  térünk rá,  ha az  elôzô bejárása  már
  139.           teljesen befejezôdött.
  140.               Ha  végponthoz  érünk  (legalsó  szint),  akkor   rögtön
  141.           elvégezzük a  statikus értékelést,  és a  minimax szabállyal
  142.           kiválasztott  értéket  azonnal  felvisszük  a  felette  lévô
  143.           szintre. Ezt az értéket a fában a gyökértôl idáig bejárt  út
  144.           mentén  ideiglenesen felvisszük  a felsôbb  szintekre is.  A
  145.           fenti értékek  azért ideiglenesek,  mert a  még be  nem járt
  146.           ágak  módosíthatják  ôket.  Ez  a  módosítás  azonban   csak
  147.           javíthatja az értékeket, így az olyan farészletekkel, melyek
  148.           már biztosan nem javítanak, nem kell foglalkoznunk.
  149.               Ezek alapján az egyszerûsítés szabályai:
  150.               @V*@N  A   keresést  nem   kell  elvégezni   az  olyan  @KVAGY@N
  151.           csomópontok alatt, melyeknél a kiértékelés eredménye  kisebb
  152.           vagy egyenlô az  ôket megelôzô @KÉS@N  csomópontok bármelyikének
  153.           ideiglenes értékénél. (Ezt  alfa levágásnak nevezik,  míg az
  154.           @KÉS@N pontok ideiglenesen felvitt értékei az alfa értékek.)
  155.               @V*@N  A  keresést szükségtelen  folytatni  minden olyan  @KÉS@N
  156.           csomópont alatt,  amelynél a  kiértékelés eredménye  nagyobb
  157.           vagy egyenlô bármely  ôt megelôzô @KVAGY@N  csomópont értékénél.
  158.           (Béta levágás, illetve béta érték.)
  159.               Természetesen  az  alfa-béta eljárás  ugyanazt  a lépést
  160.           választja  ki,  mint  a minimax,  de  a  keresési idô  jóval
  161.           rövidebb.
  162.               @KTóth      Bálint     (s4078tot@@sun10.vsz.bme.hu     vagy
  163.           @Kbali@@frey.inf.bme.hu)
  164.  
  165.  
  166.           @VPélda tik-tak-tóra@N
  167.  
  168.               A tik-tak-tó játéknál, amely  a jól ismert amôba  3*3-as
  169.           táblára   korlátozott,    egyszerûsített   változata,    egy
  170.           lehetséges @Ke(p)@N értékelô függvény lehet a következô:
  171.               @V*@N  Ha @Kp@N  nem gyôztes  állás, akkor  e(p) =  a  számunkra
  172.           szabad teljes sorok, oszlopok és átlók száma, mínusz ugyanez
  173.           az ellenfél számára.
  174.               @V*@N Ha @Kp@N állásnál mi nyerünk, akkor e(p) = plusz végtelen.
  175.               @V*@N Ha @Kp@N  állásnál az ellenfél  nyer, akkor e(p)  = mínusz
  176.           végtelen.
  177.  
  178.  
  179.           @V""Tanulás"@N
  180.  
  181.               A hagyományos algoritmusokkal -- amelyek közé a  minimax
  182.           is   tartozik   --  (rögzített   lépésmélységet   véve)  fix
  183.           játékerejû programot írhatunk. Érdekes lehetôség azonban, ha
  184.           programunk  a  lejátszott  mérkôzések  alapján   változtatja
  185.           játékát, azaz tanul.
  186.               Vizsgáljuk  meg  ezt   egy  nagyon  egyszerû   játék,  a
  187.           hatgyalog  kapcsán.  Egy  3*3-as  táblán  kezdetben  az alsó
  188.           sorban 3  világos, a  felsôben 3  sötét bábu  van. Felváltva
  189.           lépnek a sakkbeli gyalog  mozgása szerint (en passant  lépés
  190.           nincs). Egy  játékos akkor  gyôz, ha  egy gyalogot  bevisz a
  191.           szemközti oldalra, ha  az ellenfél minden  bábuja elfogyott,
  192.           vagy ha az ellenfél nem tud lépni.
  193.               Legyen  a számítógép  a sötét  (nem ô  kezd). A  játékot
  194.           elemezve  kiderül,   hogy  mindössze   24  különbözô   olyan
  195.           játékállás  van,  ahol   ô  jön,  mindegyik   állásnál  1--4
  196.           lehetséges lépéssel. Képzeljünk el a 24 állásnak megfelelôen
  197.           24   dobozt,   minden  dobozban   a   lehetséges  lépéseknek
  198.           megfelelôen   színes  golyókat.   (A  különbözô   lehetséges
  199.           lépésekhez különbözô színeket rendelünk.) A gép úgy játszik,
  200.           hogy az  adott állásnak  megfelelô dobozból  véletlenszerûen
  201.           kiválaszt  egy  golyót,  és  a  színének  megfelelôen   lép.
  202.           Semmiféle  stratégiája  nincs  tehát,  véletlenül  nyer vagy
  203.           veszít. Azonban tanulhat a korábbi mérkôzésekbôl, ha vereség
  204.           esetén a következô játszma elôtt a ""rossz" lépések  golyóit
  205.           nem teszi vissza, gyôzelem esetén pedig esetleg több  azonos
  206.           golyót   tesz   a   korábbi   egy   helyett.   îgy  hosszabb
  207.           mérkôzéssorozat után a dobozokban a jó lépéseknek  megfelelô
  208.           golyók maradnak túlsúlyban, vagyis a program játékereje nô.
  209.               A    golyók    természetesen    csak    szemléltetésként
  210.           szerepelnek. A valóságban  az egyes lépések  kiválasztásának
  211.           valószínûségét módosítjuk a tapasztalataink alapján.
  212.               A  módszer bonyolultabb  játékokban való  felhasználását
  213.           megnehezíti,   hogy   az   állás+lépés   kombinációk   száma
  214.           kezelhetetlenül nagy lehet, de még ha a memóriakapacitás nem
  215.           akadály, akkor is a kombinációk számának növekedtével  egyre
  216.           hosszabb     mérkôzéssorozat     kell     egy    elfogadható
  217.           valószínûség-eloszlás eléréséhez.
  218.               Érdekes  észrevétel, hogy  ha a  gép nem  egy  tökéletes
  219.           játékossal,  hanem  egyéni  stílust  képviselô   ellenféllel
  220.           játszik --  márpedig az  emberi játékosok  mind ilyenek  --,
  221.           akkor  a gép  játékstílusa az  ellenfeléhez idomul.  îgy  ha
  222.           hirtelen egy más stílust követô ellenfelet adunk neki, akkor
  223.           az addig tanult lépés-valószínûségek alapján esetleg gyengén
  224.           játszik. Kis idô elteltével azonban a gép ""átszokik" az  új
  225.           ellenfélre.
  226.  
  227.           @<9511\6GYALOG.GIF>■■@N  6 gyalog
  228.  
  229.  
  230.           @VAjánlott irodalom@N
  231.  
  232.               Csákány   Antal   --    dr.   Vajda   Ferenc:    Játékok
  233.           számítógéppel. Mûszaki könyvkiadó, 1980
  234.  
  235.               N.  J.  Nilsson: Problem-solving  methods  in artificial
  236.           intelligence. McGraw-Hill Book Co., 1971
  237.